2^n+1

Introduction

• We can generate a sequence of integers using the following equation:

  n	1	2	3	4	5	6	7	8
  2n + 1	3	5	9	17	33	65	129	257

• These numbers have an important property when it comes to calculating their midpoints:
  • To calculate the midpoint between two numbers, you can use this equation:
  • For example: the midpoint between 1 and 17 is:
• The midpoint between 1 and any number in the sequence 2ⁿ + 1 is equal to the previous number in the sequence
• For example:
  • The midpoint between 1 and 33 is 17
  • The midpoint between 1 and 17 is 9
  • The midpoint between 1 and 9 is 5
• Proof:
  • the midpoint between 1 and 2ⁿ + 1 is:
• A number which is in the sequence 2ⁿ + 1 can be recursively split into two segments until each segment has a size of 1:

code (Python)

from collections import deque

# The following code creates an array of numbers starting at 0 and smoothly increasing to 257

n = 3

# creates an array of 0's of size 2^n + 1
x = [0]*(2**n + 1)

# set the value for the last element
x[len(x) - 1] = 257

# we create a queue of the line segments we need to subdivide
q = deque()

# and add the first segment to it
q.append((0, len(x) - 1))

# now we go through and subdivide each segment
while len(q) != 0:
    left, right = q.popleft()
    midpoint = (left + right) // 2

    # set the midpoint to the average of the two ends
    x[midpoint] = (x[left] + x[right]) // 2

    # if the width of the segment is greater than 2 then it can be subdivided
    if right - left > 2:
        q.append((left, midpoint))
        q.append((midpoint, right))

print(x) # prints: [0, 32, 64, 96, 128, 160, 192, 224, 257]